class Trie:
    def __init__(self):
        self.nodes = {}
        self.is_word = False

    def insert(self, word):
        if not word:
            self.is_word = True
        else:
            if word[0] not in self.nodes:
                self.nodes[word[0]] = Trie()
            self.nodes[word[0]].insert(word[1:])

    def search(self, word):
        if not word:
            return self.is_word
        elif word[0] not in self.nodes:
            return False
        else:
            return self.nodes[word[0]].search(word[1:])

    def starts_with(self, word):
        if not word:
            return True
        elif word[0] not in self.nodes:
            return False
        else:
            return self.nodes[word[0]].starts_with(word[1:])

    def count_words(self, word, cur_cnt):
        if not word:
            return True if cur_cnt >= 1 and self.is_word else False
        if word[0] in self.nodes:
            start_over = False
            if self.is_word:
                start_over = root.count_words(word, cur_cnt+1)
            cont = self.nodes[word[0]].count_words(word[1:], cur_cnt)
            return start_over or cont
        else:
            return False

root = Trie()

words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
for word in words:
    root.insert(word)
result = []
for word in words:
    if root.count_words(word, 0):
        result.append(word)

print(result)